#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>
#include <cstring>

using namespace std;

EdgeNode::EdgeNode() : dest(-1), link(nullptr) {}

EdgeNode::EdgeNode(int dest, EdgeNode* link)
{
	this->dest=dest;
	this->link=link;
	
}
EdgeNode::~EdgeNode(){}

int EdgeNode::getDest()
{
	return dest;
}

EdgeNode* EdgeNode::getNext()
{
	return link;
}

void EdgeNode::setDest(int dest)
{
    this->dest = dest;
}

void EdgeNode::setNext(EdgeNode* link)
{
    this->link = link;
}

VertexNode::VertexNode() : data('\0'), firstEdge(nullptr) {}

VertexNode::VertexNode(char data, EdgeNode* firstEdge)
{
	this->data=data;
	this->firstEdge=firstEdge;
}

VertexNode::~VertexNode(){}

char VertexNode::getData()
{
	return data;
}

EdgeNode* VertexNode::getFirstEdge()
{
	return firstEdge;
}

void VertexNode::setData(char data)
{
	this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode* firstEdge)
{
	this->firstEdge = firstEdge;
}

MyGraph::MyGraph() : nodeNum(0), edgeNum(0), VexList(nullptr) {}

MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList) : nodeNum(nodeNum), edgeNum(edgeNum) 
{
        VexList = new VertexNode[nodeNum];
        for (int i = 0; i < nodeNum; i++) {
            VexList[i].setData(nodeList[i]);
        }
        for (int i = 0; i < edgeNum; i++) {
            EdgeNode* e = new EdgeNode(edgeEndList[i], VexList[edgeStartList[i]].getFirstEdge());
            VexList[edgeStartList[i]].setFirstEdge(e);
            EdgeNode* e2 = new EdgeNode(edgeStartList[i], VexList[edgeEndList[i]].getFirstEdge());
            VexList[edgeEndList[i]].setFirstEdge(e2);
        }
}

MyGraph::~MyGraph() {
        for (int i = 0; i < nodeNum; i++) {
            EdgeNode* e = VexList[i].getFirstEdge();
            while (e != nullptr) {
                EdgeNode* next = e->getNext();
                delete e;
                e = next;
            }
        }
        delete[] VexList;
    }
    
int MyGraph::getNodeNum()
{
	return nodeNum;
}

int MyGraph::getEdgeNum()
{
	return edgeNum;
}

string MyGraph::printGraph() 
{
        string s;
        for (int i = 0; i < nodeNum; i++) {
        	if(i==nodeNum-1){
        		s += VexList[i].getData();
                s += ": ";
                EdgeNode* e = VexList[i].getFirstEdge();
                while (e != nullptr) {
                    s += VexList[e->getDest()].getData();
                    if (e->getNext() != nullptr) {
                        s += ' ';
                    }
                    else {
                        break;
                    }
                    e = e->getNext();
            }
            break;
			}
            s += VexList[i].getData();
            s += ": ";
            EdgeNode* e = VexList[i].getFirstEdge();
            while (e != nullptr) {
                s += VexList[e->getDest()].getData();
                if (e->getNext() != nullptr) {
                    s += ' ';
                }
                else {
                    s += '\n';
                }
                e = e->getNext();
            }
        }
        return s;
}


void MyGraph::DFS(int v, int* visited, string& result){
    visited[v] = 1; // 标记为已访问
    result += VexList[v].getData();
    result += " ";

    int w = getFirstNeighbor(v, visited); // v的第一个邻居
    while(w != -1){ // 如果有邻居
        if(!visited[w]){ // 如果邻居未被访问，则递归访问
            DFS(w, visited, result);
        }
        w = getNextNeighbor(v, w, visited); // 继续找下一个邻居
    }
}

// BFS搜索辅助函数
void MyGraph::BFS(int v, int* visited, string& result){
    queue<int> q; // 定义一个队列
    visited[v] = 1; // 标记v已访问
    result += VexList[v].getData();
    result += " ";
    q.push(v); // 将v入队

    while(!q.empty()){
        int w = q.front(); // 取出队首元素
        q.pop();
        int u = getFirstNeighbor(w, visited);
        while(u != -1){ // 如果有邻居
            if(!visited[u]){ // 如果邻居未被访问，则标记并入队
                visited[u] = 1;
                result += VexList[u].getData();
                result += " ";
                q.push(u);
            }
            u = getNextNeighbor(w, u, visited); // 继续找下一个邻居
        }
    }
}

// 获取v的第一个未被访问的邻居
int MyGraph::getFirstNeighbor(int v, int* visited){
    EdgeNode* e = VexList[v].getFirstEdge();
    while(e){ // 遍历v的所有邻居
        if(!visited[e->getDest()]){ // 如果邻居未被访问
            return e->getDest(); // 返回邻居下标
        }
        e = e->getNext();
    }
    return -1; // 如果所有邻居都被访问过了，返回-1
}

// 获取v的下一个未被访问的邻居
int MyGraph::getNextNeighbor(int v, int w, int* visited){
    EdgeNode* e = VexList[v].getFirstEdge();
    while(e){ // 遍历v的所有邻居
        if(e->getDest() == w){ // 如果找到了w
            e = e->getNext(); // 继续往下一个邻居查找
            break;
        }
        e = e->getNext();
    }
    while(e){ // 继续往下查找未被访问的邻居
        if(!visited[e->getDest()]){
            return e->getDest(); // 找到了未被访问的邻居，返回下标
        }
        e = e->getNext();
    }
    return -1; // 如果v所有邻居都被访问过了，返回-1
}

// 深度优先搜索
string MyGraph::graph_DFS_Traverse(){
    int* visited=new int[nodeNum];
    string result = "";
   for(int i=0;i<nodeNum;i++)
    {
    	visited[i]=0;
	}
    for(int i = 0; i < nodeNum; i++){
        if(!visited[i]){ // 如果顶点i未被访问过，则从顶点i开始DFS
            DFS(i, visited, result);
        }
    }
    return result;
}

// 广度优先搜索
string MyGraph::graph_BFS_Traverse(){
    int* visited=new int[nodeNum];
    string result = "";
    for(int i=0;i<nodeNum;i++)
    {
    	visited[i]=0;
	}
    for(int i = 0; i < nodeNum; i++){
        if(!visited[i]){ // 如果顶点i未被访问过，则从顶点i开始BFS
            BFS(i, visited, result);
        }
    }
    return result;
}
